package LearnDataStructure.c_树结构.例题;
import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;

import java.util.HashMap;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-12 18:59
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
public class c_检查二叉树是否平衡 {

    public static void main(String[] args) {
        c_检查二叉树是否平衡 test = new c_检查二叉树是否平衡();
        b_MyBinaryTreebyLinked<Integer, Integer> Btree = new b_MyBinaryTreebyLinked<>();
        Btree.insert(10,9);
        Btree.insert(6,5);
        Btree.insert(4,3);
        Btree.insert(7,6);
        Btree.insert(8,7);
        Btree.insert(9,8);
        Btree.insert(2,1);
        Btree.insert(1,0);
        Btree.insert(13,0);

        System.out.println(test.useIsBalance(Btree.getRoot()));
    }

    public boolean useIsBalance(BSTNode<Integer, Integer> root) {
        return isBalance(root, new HashMap<BSTNode<Integer, Integer>, Integer>());
    }

    public boolean isBalance(BSTNode<Integer, Integer> node, HashMap<BSTNode<Integer, Integer>, Integer> heightMap) {
        if (node == null || (node.left == null && node.right == null)) {
            return true;
        }
        boolean flag = Math.abs(heightOf(node.left, heightMap) - heightOf(node.right, heightMap)) > 1;
        boolean flagOfLeft = isBalance(node.left, heightMap);
        boolean flagOfRight = isBalance(node.right, heightMap);
        return flag && flagOfLeft && flagOfRight;
    }

    /**
     * 返回的树高不是严格意义上的树高
     * 而是“严格意义上的树高 + 1”
     * @param node
     * @param heightMap
     * @return
     */
    private int heightOf(BSTNode<Integer, Integer> node, HashMap<BSTNode<Integer, Integer>, Integer> heightMap) {
        if (node == null) {//空节点视为0
            return 0;
        }
        Integer heightFromMap = heightMap.get(node);
        if (heightFromMap != null) {//这里查表的操作，节省了很多重复；
            return heightFromMap;
        }
        Integer heightOfNode = 0;
        if (node.left == null && node.right == null) {//叶子节点视为1
            heightMap.put(node,1);
        } else if (node.right == null) {
            heightOfNode = heightOf(node.left, heightMap) + 1;
            heightMap.put(node,heightOfNode);
        } else if (node.left == null){
            heightOfNode = heightOf(node.right, heightMap) + 1;
            heightMap.put(node,heightOfNode);
        } else {
            heightMap.put(node, Math.max(heightOf(node.left, heightMap), heightOf(node.right, heightMap)));
        }
        return heightOfNode;
    }
}
